在通訊錄或朋友列表裡，我們可以搜尋一個名字，就找到電話或頁面，只需要O(1)。如果想要實現這樣的操作，可以想像一種融合上一回陣列和鏈結串列的資料結構。

雜湊函式(hash function)

雜湊表是可以儲存鍵(key)和值(value)的資料結構，但它並不是像試算表一樣，只是單純地把「John Smith」和他的電話「521-1234」存在一起。它做的事情比較像是，當我們輸入John Smith，可以找到他的電話的儲存位址。而雜湊表就是透過雜湊函式的運算，來做到這種比較複雜的結構。

雜湊函式可以輸入資料，並回傳一個值。以下圖為例，雜湊函式將John Smith這個字串轉為一個雜湊值(02)，並以這個值作為陣列的索引，將John Smith的電話儲存在這個位址。換句話說，透過雜湊函式，我們可以得到一個資料存放的位址。

圖片來源：維基百科

雜湊函式的特性是：

• 具有一致性，也就是每次輸入John Smith都會輸出同樣的值。
• 不同的輸入可能會得到一樣的值(同樣的儲存位址)，也就是所謂的雜湊衝突(hash collision，也譯作碰撞) 。

雜湊衝突

理想的情況下，我們希望每個資料都有一個獨一無二的陣列位址，這樣存取所有的資料都可以實現O(1)，可是當資料量很大時，必須考慮陣列的儲存空間，而且很難實現雜湊函式回傳的值都不重複，所以必須想辦法解決雜湊衝突的問題。

舉例來說，如果有一個英文名單，我們用雜湊函式將所有人名的第一個字母轉為0-25的其中一個數字，存在長度為26的陣列中。

那很快就會出現衝突的情況，因為名字開頭字母很容易重複。衝突的一個解決方法是使用鏈結串列(linked list)，我們可以使用鏈結串列儲存索引位置相同的資料(如下圖)。這種情況的雜湊表基本上就是每個元素都是一個鏈結串列的陣列。

圖片來源：https://itnext.io/data-structures-in-js-hash-tables-app-with-react-b28b02a9e6b5

但這時候可能又有另一個問題，假設名單裡S開頭的人名特別多，那就會變成陣列中S的索引位置是一個超長的鏈結串列，而其他位址是空的，那麼其實跟直接把名單存在一個鏈結串列中沒有兩樣，存取也會變得非常沒有效率。

所以由此可知，一個好的雜湊函式要能減少衝突的發生、讓資料平均分布在雜湊表中，提升資料結構的效率。要從零開始設計出一個時間空間效率俱佳的雜湊函式不是非常容易，不過好消息是在開發時基本上不會需要自己撰寫雜湊函式，各種語言的函式庫裡都有效能不錯的雜湊函式可以直接使用。